using namespace std;
struct Node {
  int val;
  Node *next;
  Node *random;
  Node(int val) : val(val), next(nullptr), random(nullptr) {}
};

// 拷贝带自由指针的链表
Node *Copy(Node *Head) {
  Node *temp = Head;
  // 拷贝并插入链表
  while (temp != nullptr) {
    Node *t = new Node(temp->val);
    t->next = temp->next;
    temp->next = t;
    temp = t->next;
  }
  temp = Head;

  // 定位Random
  while (temp != nullptr) {
    Node *t = temp->next;
    t->random = temp->random->next;
    temp = t->next;
  }

  // 分离链表
  Node *Res = Head->next;
  temp = Head;
  while (temp != nullptr) {
    Node *t = temp->next;
    t->next = t->next->next;
    temp->next = temp->next->next;
    t = t->next;
    temp = temp->next;
  }
  return Res;
}

int main(int argc, char *argv[]) { return 0; }
